|
The Robertson–Webb protocol is a protocol for envy-free cake-cutting which is also near-exact. It has the following properties: * It works for any number (''n'') of partners. * It works for any set of weights representing different entitlements of the partners. * The pieces are not necessarily connected, i.e. each partner might receive a collection of small "crumbs". * The number of queries is finite but unbounded – it is not known in advance how many queries will be needed. The protocol was developed by Jack M. Robertson and William A. Webb. It was first published in 1997 and later in 1998. == Details == The main difficulty in designing an envy-free procedure for ''n'' > 2 agents is that the problem is not "divisible". I.e., if we divide half of the cake among ''n''/2 agents in an envy-free manner, we cannot just let the other ''n''/2 agents divide the other half in the same manner, because this might cause the first group of ''n''/2 agents to be envious (e.g., it is possible that A and B both believe they got 1/2 of their half which is 1/4 of the entire cake; C and D also believe the same way; but, A believes that C actually got the entire half while D got nothing, so A envies C). The Robertson–Webb protocol addresses this difficulty by requiring that the division is not only envy-free but also near-exact. The recursive part of the protocol is the following subroutine. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Robertson–Webb protocol」の詳細全文を読む スポンサード リンク
|